#include <bits/stdc++.h>
using namespace std;

/*
3024. 三角形类型
已解答
简单
相关标签
相关企业
提示
给你一个下标从 0 开始长度为 3 的整数数组 nums ，需要用它们来构造三角形。

如果一个三角形的所有边长度相等，那么这个三角形称为 equilateral 。
如果一个三角形恰好有两条边长度相等，那么这个三角形称为 isosceles 。
如果一个三角形三条边的长度互不相同，那么这个三角形称为 scalene 。
如果这个数组无法构成一个三角形，请你返回字符串 "none" ，否则返回一个字符串表示这个三角形的类型。

 

示例 1：

输入：nums = [3,3,3]
输出："equilateral"
解释：由于三条边长度相等，所以可以构成一个等边三角形，返回 "equilateral" 。
示例 2：

输入：nums = [3,4,5]
输出："scalene"
解释：
nums[0] + nums[1] = 3 + 4 = 7 ，大于 nums[2] = 5 。
nums[0] + nums[2] = 3 + 5 = 8 ，大于 nums[1] = 4 。
nums[1] + nums[2] = 4 + 5 = 9 ，大于 nums[0] = 3 。
由于任意两边之和都大于第三边，所以可以构成一个三角形，因为三条边的长度互不相等，所以返回 "scalene"。
提示：

nums.length == 3
1 <= nums[i] <= 100
*/

class Solution {
public:
    string triangleType(vector<int>& nums) {
        int a = nums[0], b = nums[1], c = nums[2];
        if (a + b <= c || a + c <= b || b + c <= a)     return "none";

        if (a == b && b == c)   return "equilateral";
        else if (a == b || b == c || a == c)    return "isosceles";
        else    return "scalene";
    }
};

// 今日题太简单 补充一个
/*
350. 两个数组的交集 II
已解答
简单
相关标签
相关企业
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

 

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
 

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000
 

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
*/

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> count1, count2;
        vector<int> ans;
        
        // 统计 nums1 中每个元素的出现次数
        for (int num : nums1) {
            count1[num]++;
        }
        // 统计 nums2 中每个元素的出现次数
        for (int num : nums2) {
            count2[num]++;
        }
        // 交集
        for (auto& pair : count1) {
            int num = pair.first;
            int count_in_nums1 = pair.second;
            
            // 如果 num 在 nums2 中也有出现
            if (count2.find(num) != count2.end()) {
                int count_in_nums2 = count2[num];
                // 将该元素的较小出现次数加入结果
                int count_to_add = min(count_in_nums1, count_in_nums2);
                for (int i = 0; i < count_to_add; ++i) {
                    ans.push_back(num);
                }
            }
        } 
        return ans;
    }
};

// 法二 双指针可以更快
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> target; // 用于存储结果，交集的元素
        // 对两个数组进行排序，方便后续进行比较
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        // 使用两个迭代器 it1 和 it2 分别遍历 nums1 和 nums2
        // 直到其中一个数组的遍历结束
        for (vector<int>::iterator it1 = nums1.begin(), it2 = nums2.begin(); it1 != nums1.end() && it2 != nums2.end(); ) {
            // 如果 nums1 中的当前元素小于 nums2 中的当前元素
            if (*it1 < *it2) {
                it1++; // nums1 中的元素小，向右移动 it1，继续比较下一个元素
            }
            // 如果 nums1 和 nums2 中的当前元素相等
            else if (*it1 == *it2) {
                target.push_back(*it1); // 将该元素添加到结果数组中
                it1++; // 向右移动 it1，处理下一个 nums1 中的元素
                it2++; // 向右移动 it2，处理下一个 nums2 中的元素
            }
            // 如果 nums1 中的当前元素大于 nums2 中的当前元素
            else if (*it1 > *it2) {
                it2++; // nums2 中的元素小，向右移动 it2，继续比较下一个元素
            }
        }  
        return target; // 返回交集结果
    }
};
